package leetcode.code039;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution1 extends Solution39 {

	@Override
	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		Arrays.sort(candidates);
		return combinationSum(candidates, 0, target);
	}

	private List<List<Integer>> combinationSum(int[] candidates, int start, int target) {
//		System.out.println("范围 : " + start + "目标 ：" + target);
		List<List<Integer>> result = new ArrayList<>();
		for (int i = start; i < candidates.length; i++) {
			int num = candidates[i];
			int times = target / num;
			while (times > 0) {
				List<Integer> part1 = this.dupNum(num, times);
				int cha = target - num * times;
				if (cha == 0) {
					result.add(new ArrayList<>(part1));
				} else if (cha > 0 && i + 1 < candidates.length && cha >= candidates[i + 1]) {
					List<List<Integer>> part2s = this.combinationSum(candidates, i + 1, cha);
					for (List<Integer> part2 : part2s) {
						List<Integer> temp = new ArrayList<>();
						temp.addAll(part1);
						temp.addAll(part2);
						result.add(temp);
					}
				}
				times--;
			}
		}
		return result;
	}

	private List<Integer> dupNum(int num, int times) {
		List<Integer> temp = new ArrayList<>();
		for (int i = 0; i < times; i++) {
			temp.add(num);
		}
		return temp;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		System.out.println("===========================");
		so.debug2();
		System.out.println("===========================");
		so.debug3();
		System.out.println("===========================");
		so.debug4();
		System.out.println("===========================");
		so.debug5();
		System.out.println("===========================");
	}

}
